package algo;

import model.tsp.Problem;
import model.tsp.Solution;
import util.PrinterUtils;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

import static algo.Operator.exchangeOperator;
import static algo.Operator.leftShiftOperator;
import static algo.Operator.relocatedOperator;
import static algo.Operator.rightShiftOperator;
import static algo.Operator.twoOptOperator;

public class VariableNeighborhoodSearch2 extends HeuristicSearch {


    public VariableNeighborhoodSearch2(Problem problem) {
        super(problem);
    }

    public void solve() {
        Solution initSolution = initial();
        PrinterUtils.printTspResult("vns init", initSolution);
        Solution finalSolution = improve(initSolution);
        PrinterUtils.printTspResult("vns final", finalSolution);
    }

    private Solution initial() {
        GreedySearch greedySearch = new GreedySearch(problem);
        return greedySearch.search();
    }

    private Solution improve(Solution solution) {
        return localSearch(solution);
    }


    private Solution shake(List<Integer> permutation) {
        Random random = new Random();
        random.setSeed(123);
        int first = random.nextInt(permutation.size() - 1) + 1;
        int second = random.nextInt(permutation.size() - 1) + 1;
        if (first > second) {
            int tmp = first;
            first = second;
            second = tmp;
        }
        List<Integer> newPermutation = exchangeOperator(permutation, first, second);
        int cost = calculateFitness(newPermutation);
        return new Solution(newPermutation, cost);
    }

    private Solution localSearch(Solution solution) {
        List<Integer> bestPermutation = solution.getPermutation();
        int bestCost = solution.getCost();
        Random random = new Random(2345);

        int iterMax = 2000;
        int k = 0;
        while (k++ < iterMax) {
            List<Integer> permutation = new ArrayList<>(bestPermutation);
            // shaking扰动
            if (k == 1) {
                Solution shakeSolution = shake(bestPermutation);
                permutation = shakeSolution.getPermutation();
            }

            int first = random.nextInt(permutation.size() - 1) + 1;
            int second = random.nextInt(permutation.size() - 1) + 1;
            if (first > second) {
                int tmp = first;
                first = second;
                second = tmp;
            }

            List<Integer> relocateSolution = relocatedOperator(permutation, first, second);
            int cost = calculateFitness(relocateSolution);
            if (cost < bestCost) {
                bestPermutation = relocateSolution;
                bestCost = cost;
                k = 0;
                continue;
            }

            List<Integer> twoOptSolution = twoOptOperator(permutation, first, second);
            cost = calculateFitness(twoOptSolution);
            if (cost < bestCost) {
                bestPermutation = twoOptSolution;
                bestCost = cost;
                k = 0;
                continue;
            }

            List<Integer> exchangeSolution = exchangeOperator(permutation, first, second);
            cost = calculateFitness(exchangeSolution);
            if (cost < bestCost) {
                bestPermutation = exchangeSolution;
                bestCost = cost;
                k = 0;
                continue;
            }

            int step = 1;
            while (step++ < (second - first)) {
                List<Integer> rightShiftSolution = rightShiftOperator(permutation, first, second, 1);
                cost = calculateFitness(rightShiftSolution);
                if (cost < bestCost) {
                    bestPermutation = rightShiftSolution;
                    bestCost = cost;
                    k = 0;
                    continue;
                }
            }

            step = 1;
            while (step++ < (second - first)) {
                List<Integer> leftShiftSolution = leftShiftOperator(permutation, first, second, 1);
                cost = calculateFitness(leftShiftSolution);
                if (cost < bestCost) {
                    bestPermutation = leftShiftSolution;
                    bestCost = cost;
                    k = 0;
                    continue;
                }
            }
        }

        return new Solution(bestPermutation, bestCost);
    }

}
